class Solution():
    def quickSort(self, array, low, high):
        if low >= high:
            return array
        i, j = low, high
        pk = array[i]
        while i < j:
            while i < j and array[j] >= pk:
                j -= 1
            array[i] = array[j]
            while i < j and array[i] <= pk:
                i += 1
            array[j] = array[i]
        array[j] = pk
        self.quickSort(array, low, i - 1)
        self.quickSort(array, i + 1, high)
        return array

    # 牛逼的三行快排
    def nb_quickSort(self, L):
        if len(L) <= 1: return L
        return self.nb_quickSort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + self.nb_quickSort([ge for ge in L[1:] if ge >= L[0]])

s = Solution()
print(s.quickSort([9,8,5,7,6,2,4,5,4,5,1,1,2], 0, 12))
print(s.nb_quickSort([9,8,5,7,6,2,4,5,4,5,1,1,2]))